package 动态规划;

public class 最佳观光组合 {
    public int maxScoreSightseeingPair(int[] values) {
//        dp来做，稍微给这个公式变形成A[i]+i+A[j]-j，
//        这样就可以看成是左A[i]+i和右A[j]-j两部分和的最大值。
//        随着遍历数组，我们对两部分和取最大值，并且若当前的值—下标对之和比之前更大，
//        我们就更新left部分的值即可。
        int left = values[0],res=0;
        for (int i = 1; i < values.length; i++) {
            res = Math.max(res,left+values[i]-i);
            left = Math.max(left,values[i]+i);
        }
        return res;
    }
}
